Nettalk

From: Paul Singleton
Subject: Re: Good Examples of Properly Commented Prolog Code

Roberto Bagnara wrote:
>> 6.6 Test every predicate by forcing it to backtrack.

> ...I would give the explicit advice of checking that
> failing back into the predicate _really__does_ (as apposed to
> _apparently_does_) the right thing. For example, especially (but
> not only) when the predicate at hand is meant to be deterministic
> or semideterministic, checking that choicepoints left around are as
> expected is often the source of interesting surprises.

Is there a reliable programmatic way of checking whether a goal leaves a choicepoint? e.g.

   succeeds_without_choicepoint(Goal) :-
       statistics(localused, L1),
       call(Goal),
       statistics(localused, L2),
       L1 >= L2.

   ?- succeeds_without_choicepoint(member(1, [1,2,3])).

   No
   ?- succeeds_without_choicepoint(memberchk(1, [1,2,3])).

   Yes

but I guess all sorts of things could go wrong with this?

Nested Predicates?

From: Maurizio Colucci

Whenever I realize that a predicate is only used inside another one, I miss the ability to nest predicates. It would make the code more readable: instead of seeing a flat space, the reader would only see a few top-level predicates, and make his way into the code in a hierarchical way, like traversing a tree.

Is there any plan for such an addition to SWI? Is there any standard?
Is there any counter-argument or alternative solution? Thanks

From: Paulo Moura
Subject: Re: Nested Predicates?

You may use SWI-Prolog module system or Logtalk objects to encapsulate auxiliary predicates and expose only a "few top-level predicates" as you write above.

From: Jan Wielemaker
To: SWI-Prolog mailing list
Subject: Re: [SWIPL] Nested predicates?
Date: Sun, 26 Mar 2006 17:44:26 +0100

Maurizio Colucci wrote:
> Whenever I realize that a predicate is only used inside another one, I
> miss the ability to nest predicates. It would make the code more
> readable: instead of seeing a flat space, the reader would only see a
> few top-level predicates, and make his way into the code in a
> hierarchical way, like traversing a tree.
>
> Is there any plan for such an addition to SWI? Is there any standard?

I think the answer is 'no no'.

> Is there any counter-argument or alternative solution? Thanks

As suggested, modules (or objects) are the standard way around. As for counter arguments, I think is needlessly complicates syntax and would require various new primitives to examine the program, do meta-interpretation, etc. If there is something to be nested, modules come to mind as the first candidate. The currently flat module space is getting a problem as the amount of reusable code grows, especially if people aren't careful to use some kind of prefix to avoid name-clashes.

From: Richard A. O'Keefe
To: SWI-Prolog mailing list
Subject: Re: [SWIPL] Nested predicates?
Date: Mon, 27 Mar 2006 15:34:55 +1200 (NZST)

Maurizio Colucci wrote:
> Whenever I realize that a predicate is only used inside another one,
> I miss the ability to nest predicates.

When I started writing Prolog code at Edinburgh, I used to indent auxiliary predicates. Taking the example of calculating Fibonacci numbers, which happened to come up in another mailing list, I would have written

    :- mode fib(+, ?).

    fib(0, 1) :- !.
    fib(N, F) :-
    integer(N), N > 0,
    fib(N, 1, 1, S),
    F = S.

    :- mode fib(+, +, +, -).

    fib(1, X, _, X) :- !.
    fib(N, X, Y, S) :-
        N1 is N - 1,
        W is X + Y,
        fib(N1, W, X, S).

Lawrence Byrd looked at some of my code, and said "You really miss Algol, don't you?"

> It would make the code more readable:

Once I got used to the fact that Prolog really isn't that kind of language, I realised that no, it *didn't* make the code more readable.

> instead of seeing a flat space, the reader would only see a
> few top-level predicates, and make his way into the code in a
> hierarchical way, like traversing a tree.

This is one of the reasons. Things are like a tree much less often than one thinks. An auxiliary predicate having been defined, you often find uses for it elsewhere. (For example, my fib/3 can also be used to calculate Lucas numbers.)

> Is there any plan for such an addition to SWI?

I hope not.

> Is there any standard?

Yes. The standard is "don't do that".

> Is there any counter-argument or alternative solution?

The readability of your code depends far more on the quality of your comments than on nesting. I don't really believe that there is any problem here that needs a solution. The way to encapsulation stuff is to use modules.

Oddly enough, I've recently been suggesting child modules for another similar language in another mailing list. Child modules would be nice for very large systems. Curiously enough, I know of two languages that *had* hierarchical modules (SETL and Lisp) which dropped them (ISETL and SETL2 have a flat module name space, as does Common Lisp).

From: Richard A. O'Keefe
To: SWI-Prolog mailing list
Subject: RE: [SWIPL] Nested predicates?
Date: Tue, 28 Mar 2006 14:07:09 +1200 (NZST)

Ralf Lammel wrote, rather strangely,
> I don't see any convincing argument in Richard O'Keefe's email that
> explains why "nested predicates" in Prolog are *conceptually* less
> sensible than local function definitions in Algol, Haskell, Pascal, ...

That's because I didn't even *try* to provide such an argument, and that's because I did not make any such claim.

I did not say, sing, whistle, hum, inscribe on clay, stone, sand, wax, or any other material, transmit by Morse code, mental telepathy, pheromones, or any other means, nor cause nor induce any other person to do so, any statement which could be held as meaning or implying that "nested predicates are conceptually less sensible in Prolog".

They aren't *necessary*.
They would greatly complicate the language.
They would greatly increase the difficulty of writing tools to process the language.
Using Prolog since October 1979 has shown me that they would have VERY low payoff.

But none of that says that they are "conceptually less sensible".

Of *course* you could have a logic programming language with nested predicates, and if you want one, by all means go ahead and design and implement it. Just don't expect anyone else to pay the price.

> Richard says that "Things are like a tree much less often than
> one thinks." but how does this explain that local definitions
> are used quite a bit in say Haskell

As it happens, between the time I wrote this sentence and the time I'll write the next one, I'm going to give a 2 hour lecture on Haskell programming [left at 10:54am]. [returned at 1:06pm] Can I make the obvious point that "Things are like a tree much less often than one thinks" was a statement about Prolog, so cannot fairly be expected to explain anything about Haskell?

Let me also make the obvious point that Haskell *needs* local definitions because it doesn't have unification. Consider the following Haskell code for computing the "percentage bend correlation":

pbcor = pbcor_gen 0.1

pbcor_gen beta pairs =
    dot as bs / sqrt (dot as as * dot bs bs)
    where
    dot xs ys = sum [x*y | (x,y) <- zip xs ys]
    as = scaled_and_clamped xs
        bs = scaled_and_clamped ys
        (xs, ys) = unzip pairs

        scaled_and_clamped xs =
            [(0-1) `max` (1 `min` ((x-phi)/omega)) | x <- xs]
            where
        phi = (omega*fromIntegral (i2-i1) + s)/fromIntegral (n-i1-i2)
                s = sum ((n-i1-i2) `take` (i1 `drop` sorted_xs))
                sorted_xs = sort xs
        i1 = length [1 | x <- xs, (x-median)/omega < -1]
        i2 = length [1 | x <- xs, (x-median)/omega > 1]
                omega = sort ws !! (floor ((1 - beta)*fromIntegral n) - 1)
                ws = [abs (x - median) | x <- xs]
                median = (sorted_xs !! h + sorted_xs !! (n-1-h)) / 2
                h = n `div` 2
                n = length xs

In this Haskell code, there are
     2 nested functions
    14 nested variables
     5 list comprehensions

What does a Haskell compiler do with the nested functions? IT MOVES THEM OUT! (This is called 'lambda lifting', IIRC.) We can do the same for Prolog.

pbcor(Pairs, R) :-
    pbcor(Pairs, 0.1, R).

pbcor(Pairs, Beta, R) :-
    unzip(Pairs, Xs, Ys),        % no let/where is needed for
    scaled_and_clamped(Xs, Beta, As),   % introducing Xs, Ys, As, or Bs.
    scaled_and_clapmed(Ys, Beta, Bs),   % (nor AA, AB, or BB).
    dot(As, As, AA),
    dot(As, Bs, AB),
    dot(Bs, Bs, BB),
    R is AB/sqrt(AA*BB).

scaled_and_clamped(Xs, Beta, Ys) :-
    length(Xs, N),            % once again, there is no need
    H1 is N // 2,            % for any let/where just so that
    H2 is N - 1 - H1,            % we can define local variables!
    msort(Xs, Sorted_Xs),
    nth0(H1, Sorted_Xs, Mid_Lo),
    nth0(H2, Sorted_Xs, Mid_Hi),
    Median is (Mid_Lo + Mid_Hi)/2,
    Median_Shift is -Median,
    scaled_and_shifted(Xs, 1, Median_Shift, Ms),
    abs_list(Ms, Ws),
    msort(Ws, Sorted_Ws),
    Omega_Pos is floor((1 - Beta)*N) - 1,
    nth0(Omega_Pos, Sorted_Ws, Omega),
    count(X, Ms, X < -Omega, I1),
    count(X, Ms, X > Omega, I2),
    I3 is N - I1 - I2,
    drop(I1, Sorted_Xs, Mid_And_High_Xs),
    take(I3, Mid_And_High_Xs, Mid_Xs),
    sum(Mid_Xs, S),
    Phi is (Omega*(I2-I1) + S)/I3,
    Scale is 1.0/Omega,
    Shift is -Phi/Omega,
    scale_and_shift(Xs, Scale, Shift, Scaled_And_Shifted),
    clamp(Scaled_And_Shifted, -1, 1, Ys).

/* Library predicates */
/* All of these are or should be in your Prolog library,
    possibly with a different name and interface,
    except for scale_and_shift/4, clamp/4, abs_list/2.
    I'm a bit embarrassed about those, to tell you the
    truth, but NONE of these functions is coupled to its
    uses in the preceding code; ALL are reusable.
*/
unzip([], [], []).
unzip([(X,Y)|Pairs], [X|Xs], [Y|Ys]) :-
    unzip(Pairs, Xs, Ys).

dot(Xs, Ys, Dot) :-
    dot(Xs, Ys, 0, Dot).

% NB: at first sight, dot/4 should be private to dot/3,
% but I have *VERY* often had a use for calling it directly
% instead of calling dot/3.

dot([], [], Dot, Dot).
dot([X|Xs], [Y|Ys], Dot0, Dot) :-
    Dot1 is Dot0 + X*Y,
    dot(Xs, Ys, Dot1, Dot).

sum(Xs, Sum) :-
    sum(Xs, 0, Sum).

% NB: at first sight, sum/3 should be private to sum/2,
% but again, I find it useful to call sum/3 directly about
% as often as it's useful to call sum/2.

sum([], Sum, Sum).
sum([X|Xs], Sum0, Sum) :-
    Sum1 is Sum0 + X,
    sum(Xs, Sum1, Sum).

scale_and_shift([], _, _, []).
scale_and_shift([X|Xs], A, B, [Y|Ys]) :-
    Y is A*X+B,
    scale_and_sfhit(Xs, A, B, Ys).

clamp([], _, _, []).
clamp([X|Xs], L, U, [Y|Ys]) :-
    (   X < L -> Y = L
    ;   X > U -> Y = U
    ;            Y = X
    ),
    clamp(Xs, L, U, Ys).

count(Template, List, Condition, Count) :-
    findall(*, ( member(Template, List), Condition ), L),
    length(L, Count).

abs_list([], []).
abs_list([X|Xs], [Y|Ys]) :-
    Y is abs(X),
    abs_list(Xs, Ys).

drop(N, [_|Xs], Ys) :- N > 0, !,
    N1 is N - 1,
    drop(N1, Xs, Ys).
drop(_, Xs, Xs).

take(N, [X|Xs], [X|Ys]) :- N > 0, !,
    N1 is N - 1,
    take(N1, Xs, Ys).
take(0, _, []) :- !.
take(_, [], []).

nth0(N, List, X) :-
    (   integer(N) ->
    N >= 0,
    nth0i(N, List, X)
    ;   var(X) ->
    nth0v(L, X, 0, N)
    ;   abort
    ).

nth0v([X|_], X, N, N).
nth0v([_|Xs], X, N0, N) :-
    N1 is N0 + 1,
    nth0v(Xs, X, N1, N).

nth0i(N, {X|Xs], V) :-
    (   N =:= 0 -> V = X
    ;   N1 is N - 1,
        nth0i(N1, Xs, V)
    ).

Oh, let's clean that up a bit. The preferred way to take a section of a list in Prolog is not to use take and drop but to use length:sublist.

    drop(I1, Sorted_Xs, Mid_And_High_Xs),
    take(I3, Mid_And_High_Xs, Mid_Xs),

should be

    length:sublist(Sorted_Xs, Mid_Xs, I1, I3, I2)

We can do list comprehensions with findall/3:

    Median_Shift is -Median,
    scaled_and_shifted(Xs, 1, Median_Shift, Ms),
    abs_list(Ms, Ws),

could be

    findall(W, (member(X, Xs), W is abs(X-Median)), Ws)

and

    Scale is 1.0/Omega,
    Shift is -Phi/Omega,
    scale_and_shift(Xs, Scale, Shift, Scaled_And_Shifted),
    clamp(Scaled_And_Shifted, -1, 1, Ys).

could be

    findall(Y, ( member(X, Xs), Y is min(1, max(-1, (X-Phi)/Omega)) ), Ys)

I just wish findall/3 were as cheap as "map", but it isn't.

> but they wouldn't be used in Prolog, if they were enabled?

I dare say they WOULD be used in Prolog. *BUT* "enabling" nested definitions in Prolog would not be a simple matter of flipping a switch (as "enabled" suggests), but of fairly major design and implementation work. And the compiler would have to implement them the way a Haskell compiler does: by turning them into UN-nested functions.

> I could try to guess that this
> may have something to do with the more pervasive higher-order
> style in Haskell, but I would think that people also use
> "where"s in first-order Haskell programs.

Of course they do. They use 'where' a LOT in Haskell, for the simple reason that if you want to name an intermediate result (that is NOT a function) you have to use "let" or "where".

> I don't have metrics results that back up my guess. I could
> come up with some other guesses; I have indeed some candidates,
> but perhaps someone *knows*.

Take a look at Mercury. It combines logic programming and functional programming, and it is quite good at supporting higher order programming, and it HAS anonymous nested function and predicate definitions (tamed by the mode system so that higher-order unification is never needed).

In short, if you don't like Prolog, try Mercury. It may be exactly what you want. (And it requires a very complex implementation, but someone has already done that.)

> In fact, the (first-order) fib function appears to me as a reasonable
> example of a function that benefits from a local helper. Richard says
> "An auxiliary predicate having been defined, you often find uses for it
> elsewhere. (For example, my fib/3 can also be used to calculate Lucas
> numbers.)" I get the point for fib/3 but the general argument seems to
> lead to a slippery slope because it sounds a bit like let's presume most
> abstractions are reusable in perhaps unanticipated ways, so better
> expose them, so better export almost everything.

No, I did *NOT* say "export". In fact I said the explicit opposite of that. I said to ENCAPSULATE functions that would have been nested, but to encapsulate them using MODULES.

In fact the example I presented above is a good (because entirely honest) demonstration of my point: with the single exception of scaled_and_clamped/3, every single auxiliary predicate I needed either *was* in my library already or could profitably be put there. Ones that weren't already in the library would not be *EXPORTED*; they would be kept at top level until they were needed in another module at which point they would be moved out of this module entirely and into an appropriate module in the library.

> Below, I list some ways to transcribe O'Keefe's fib to Haskell. The
> first one is the more sensible one for the case of fib; it associates
> the helper with the relevant equation. The other two variations
> illustrate notational options -- one can make it so that a helper is
> accessible by several "cases". In reality, one uses local functions for
> more than just "hiding" or "grouping with a client", i.e., they are used
> as means to take advantage of the existing argument bindings for the
> parent. The fib example cannot make interesting use of this possibility
> but here is a lambda-dropped version of append that binds ys at the top:
>
> append xs ys = append xs
> where
>   append [] = ys
>   append (x:xs) = x : append xs

And do you know what a Haskell compiler does with this? It turns it into

    append xs ys = (append' ys) xs

    append' ys [] = ys
    append' ys (x:xs) = x : (append' ys) xs

which is just the original definition twisted around a bit. One has to ask, what *is* the point? Why move something in when it's going to be moved straight out again?

In fact there is a specific feature of Haskell which means that nested functions are often better as un-nested functions (with export being controlled in Haskell, as in SWI Prolog, by the module system). That's the well known scope-of-type-variables problem.

> -- Attach the helper to the relevant equation
> fib 0 = 1
> fib n = fib n 1 1
> where fib 1 x _ = x
>        fib n x y = fib (n-1) (x+y) x

Which the Haskell compiler turns into

    fib 0 = 1
    fib n = fib' n 1 1

    fib' 1 x _ = x
    fib' n x y = fib' (n-1) (x+y) x

The nested function is HARDER to read because the human reader has to ask "WHY is this function nested? HOW is it coupled to its surroundings?" In this case, the answer turns out to be "it isn't", which causes a justified feeling of resentment: "why, Mr Author, did you make me do all that decoding work for nothing?"

> -- Factor for a single binding, multiple RHSs
> fib n | n == 0    = 1
>       | otherwise = fib n 1 1
> where fib 1 x _ = x
>        fib n x y = fib (n-1) (x+y) x

This has all the disadvantages of the previous version, plus some scoping weirdness: 'where' definitions are available in multiple alternatives for a single rule, but not for multiple rules. Again, this is far more readable if the nested function is NOT nested.

Just to try, possibly vainly, to avoid any misconception: I am NOT saying that nested functions are undesirable or inappropriate or anything like that in Haskell. What I *am* saying is that if an auxiliary function isn't *coupled* to its context through one or more shared variables, it is almost always better to un-nest it. (I wrote the pbcor function at the top, and the only reason dot is declared inside is sheer laziness; I am sorry I did that.)

From: Bart Demoen
To: SWI-Prolog mailing list
Subject: Re: [SWIPL] Nested predicates?
Date: Tue, 28 Mar 2006 21:47:39 +0200

Richard A. O'Keefe wrote:
> if an auxiliary function isn't *coupled* to its context through one
> or more shared variables, it is almost always better to un-nest it.
> ...
> the only reason dot is declared inside is sheer laziness

[I didn't read all of Richard's mail]

I find the ability to nest functions/predicates attractive because I can often vouch for "this definition is correct when used as in the context just surrounding it" but not for any larger context. That's lazyness, or lack of time, but most of all it is trying to err on the safe side: don't make things public that you're not prepared to "maintain".

"*coupled* to its context through one or more shared variables" is one aspect of coupling to a context - it couls also be because of preconditions that are context dependent.

From: Richard A. O'Keefe
To: SWI-Prolog mailing list
Subject: Re: [SWIPL] Nested predicates?
Date: Wed, 29 Mar 2006 16:51:25 +1200 (NZST)

I wrote:
>> if an auxiliary function isn't *coupled* to its context through one
>> or more shared variables, it is almost always better to un-nest it.

Bart Demoen replied:
> I find the ability to nest functions/predicates attractive because I
> can often vouch for "this definition is correct when used as in the
> context just surrounding it" but not for any larger context.

This brings us back to the discussion about style that we were having a while back. What is to the advantage of the *writer* of a piece of code is not always to the advantage of the *reader*.

To me the important question is "how will someone ELSE, reading this code, KNOW what the relevant context actually is?"

> That's lazyness, or lack of time, but most of all it is trying to err
> on the safe side: don't make things public that you're not prepared to
> "maintain".

This is a straw man. Consider this table:

	public	not public
nested	possible	possible
not nested	possible	possible

I have been, and remain, concerned solely with the nested/not nested question. This is entirely orthogonal to the public/not public question. All four combinations are theoretically possible and all four of them are supported in some programming language or other. (Lisp, for instance.)

Making something "not nested" is very very VERY different from making it public.

> "*coupled* to its context through one or more shared variables" is one
> aspect of coupling to a context - it could also be because of
> preconditions that are context dependent.

Right. Which is why simply putting one routine inside another one is NOT enough all by itself. A future reader (including yourself a few months later) needs to know WHAT the relevant context is. That means commenting it.

Now, take an example from my earlier message:

    nth0(N, List, X) :-
    (   integer(N) ->
        N >= 0,
        nth0i(N, List, X)
    ;   var(X) ->
        nth0v(L, X, 0, N)
    ;   abort
    ).

    nth0v([X|_], X, N, N).
    nth0v([_|Xs], X, N0, N) :-
    N1 is N0 + 1,
    nth0v(Xs, X, N1, N).

    nth0i(N, {X|Xs], V) :-
    (   N =:= 0 -> V = X
    ;   N1 is N - 1,
        nth0i(N1, Xs, V)
    ).

nth0/3 is exported from the module it is defined in. It is "public" and "not nested".

nth0v/4 and nth0i/3 are *not* exported from that module. They are "not public" and "not nested".

Making them "not nested" means a big benefit for a human reader: whatever the context might be (if any) that links them to nth0/3, it *isn't* shared variables. When I am trying to understand a variable in nth0i/3, I do not have to look anywhere else at all.

There _is_ a coupling between these predicates and their caller, and in the real code, it's explained in the comments I stripped out to keep the previous message short:

    %. nth0v(?List: list(T), ?Element: T, +N0: integer, -N: integer).
    %. nth0i(?List: list(T), ?Element: T, +I: integer).

So, would this be better if we made these predicates nested?

    nth0(N, List, X) :-
    (   integer(N) ->
        N >= 0,
        nth0i(N, List, X)
        where {|
        nth0i(N, {X|Xs], V) :-
            (   N =:= 0 -> V = X
            ;   N1 is N - 1,
            nth0i(N1, Xs, V)
            )
        |}
    ;   var(X) ->
        nth0v(L, X, 0, N)
        where {|
        nth0v([X|_], X, N, N);;
        nth0v([_|Xs], X, N0, N) :-
            N1 is N0 + 1,
            nth0v(Xs, X, N1, N)
        |}
    ;   abort
    ).

I don't think so. We run into a prlblem: are N and X the same thing inside nth0i/3 as they are in nth0/3, and if not, why not? The sheer bulk makes this version of nth0/3 hard to read.

But most tellingly, there is *also* in that library a predicate

    nth1(N, L, X) :-
        (   integer(N) ->
            N >= 1,
            M is N - 1,
            nth0i(M, L, X)
        ;   var(N) ->
            nth0v(L, X, 1, N)
        ;   abort
        ).

Yes, those predicates depended on instantiation state guaranteed by the caller, BUT another caller within the same module could make the same guarantees.

If routines are unnested ("lambda-lifted") and the context conditions are made EXPLICIT, then

the routines, though still private, are available for further use within the same module
whether they are used again or not, the life of human readers is made vastly simpler because they are TOLD what they would otherwise have to puzzle out.

Make no mistake. I have known and loved Algol-like languages for a long time. (The second non-trivial program I ever worked on was a port of Wirth's Euler compiler.) I have known and loved Lisp-like languages for a long time. I regard the lack of nesting functions in C++ as a serious flaw. Give me a language that allows nested definitions, and I will use them.

I'm not arguing that nested definitions are a bad idea.
I'm making two claims:

*implicit* coupling is not good.
One of the main advantages of Prolog is its simplicity; adding nested definitions to Prolog would make it a much more complicated language, and empirically, the benefit would not be great.

As I've said before, if I want Mercury, I know where to find it. (~/export/mercury.d/, as it happens.)

Content: